504. Парковка

Вы хотите запарковать машины гостей, приехавших на вечеринку, на улице. Согласно правилам нельзя парковать машины:

1. перед частным выездом;

2. на остановке автобуса, а также менее чем в 10 метрах до нее;

3. на пешеходном переходе, а также менее чем в 5 метрах до него или после него.

Вы составили планы окрестных улиц, разбив их на участки длиной 5 метров (это минимальная длина для парковки автомобиля). Участок с выездом на плане обозначается символом 'D', автобусные остановки – 'B', переходы – 'S', прочие – '-'. Движение на улице односторонее и организовано слева направо.

Напишите программу, которая для каждой улицы определит число парковочных мест.

Вход. В первой строке содержится количество улиц n (1 ≤ n ≤ 100). Далее следует n строк, содержащих планы улиц, каждая из которых имеет длину от 1 до 50 символов и содержит только 'D', 'B', 'S' и '-'.

Выход. Для каждого плана улицы вывести строку, содержащую количество парковочных мест.

Пример входа	Пример выхода
3 ---B--S-D--S-- DDBDDBDDBDD --S--S--S--S—-	4 0 2

РЕШЕНИЕ

строки

Анализ алгоритма

Перебираем все возможные участки длиной 5 метров улицы и проверяем, можно ли в них припарковать автомобиль. Пусть план улицы хранится в символьном массиве s. Тогда на участке s[i] можно припарковаться, если одновременно выполняются следующие условия:

· s[i] = ‘-‘, то есть участок свободен;

· s[i – 1] ≠ ‘S’ и s[i + 1] ≠ ‘S’, то есть рядом нет пешеходного перехода;

· s[i + 1] ≠ ‘B’ и s[i + 2] ≠ ‘B’, то есть впереди на расстоянии до 10 метров нет автобусной остановки. Отметим, что согласно условию задачи припарковаться сразу за автобусной остановкой можно;

Пример

Для первого примера рассмотрим все положения возможной парковки. Они обозначены зеленым цветом.

Реализация алгоритма

План улицы храним в строке s.

char s[100];

Для каждого теста читаем план улицы в символьный массив s, начиная с первой позиции (для удобства обработки).

scanf("%d\n",&n);

while(n--)

{

gets(s+1); res = 0;

for(i = 1; i <= strlen(s+1); i++)

Для каждого участка s[i] проверяем, можно ли на нем припарковаться.

if ((s[i] == '-') && (s[i+1] != 'S') && (s[i-1] != 'S') &&

(s[i+1] != 'B') && (s[i+2] != 'B')) res++;

Выводим количество возможных парковочных мест на текущей улице.

printf("%d\n",res);

}

Java реализация

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

while(n-- > 0)

{

int res = 0;

char[] s = (" " + con.next() + " ").toCharArray();

for(int i = 1; i < s.length - 2; i++)

if ((s[i] == '-') && (s[i+1] != 'S') &&

(s[i-1] != 'S') && (s[i+1] != 'B') &&

(s[i+2] != 'B')) res++;

System.out.println(res);

}

con.close();

}

}